package com.zh.note.leetcode.backtracking;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 77. 组合
 * 输入：n = 4, k = 2
 * 输出：
 * [
 * [2,4],
 * [3,4],
 * [2,3],
 * [1,2],
 * [1,3],
 * [1,4],
 * ]
 */
public class LC_77_combine {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();// 存放符合条件结果的集合
        Deque<Integer> path = new LinkedList<>();// 用来存放符合条件结果
        dfs(n, k, 1, path, res);
        return res;
    }

    /**
     * @param n
     * @param k
     * @param startIndex 每次开始的其实位置
     * @param path
     * @param res
     */
    // public void dfs(int n, int k, int startIndex, Deque<Integer> path, List<List<Integer>> res) {
    //     // 递归出口
    //     if (path.size() == k) {
    //         res.add(new ArrayList<>(path));
    //         return;
    //     }
    //     for (int i = startIndex; i <= n; i++) {// 控制树的横向遍历
    //         path.addLast(i);// 处理节点
    //         dfs(n, k, i + 1, path, res);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    //         path.removeLast(); // 回溯，撤销处理的节点
    //     }
    // }
    // 剪枝
    public void dfs(int n, int k, int startIndex, Deque<Integer> path, List<List<Integer>> res) {
        // 递归出口
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {// 控制树的横向遍历
            path.addLast(i);// 处理节点
            dfs(n, k, i + 1, path, res);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            path.removeLast(); // 回溯，撤销处理的节点
        }
    }

    public static void main(String[] args) {
        // combine(4, 2);
    }
}
